package ds.array;

/**
 * 基于线性查找的无序数组
 * 
 * 插入快 O(1)
 * 
 * 查找、删除慢 O(N)
 **/
public class HighArray {

	private long[] a; // ref to array a
	private int nElems; // number of data items
	//-----------------------------------------
	public HighArray(int max) //constructor
	{
		a = new long[max]; // create the array
		nElems = 0; // no items yet
	}
	
	private int find(long searchKey) // find specified value
	{
		int j;
		for(j=0;j<nElems;j++)  // for each element
		{
			if(a[j] == searchKey) // found item?
				break;            // if found, exit loop before end
		}
		if(j==nElems) // gone to end?
			return -1; // can't find it,return false
		else
			return j; // we've found it
	} // end find()
	
	public void insert(long value) // put element into array
	{
		if(nElems >= a.length)
		{
			System.out.println("数组已满，插入将无效"); //TODO
			return;
		}
		a[nElems] = value; // insert it
		nElems++; // increment size
	}
	
	public boolean delete(long value)
	{
		int j;
		j = find(value);
		if(j!=-1)
		{
			for(int k=j;k<nElems-1;k++)  // move higher ones down; //TODO
				a[k]=a[k+1];
			nElems--;
			return true;
		}
		else  
			return false;
	} // end delete()
	
	public int deleteAll(long value) {
		int j,delCount = 0;
		while((j=find(value))!=-1){
			for(int k=j;k<nElems-1;k++)  // move higher ones down; //TODO
				a[k]=a[k+1];
			nElems--;
			delCount++;
		}
		return delCount;
	}
	
	public void display() // displays array contents
	{
		for(int j=0;j<nElems;j++) // for each element
		{
			System.out.print(a[j] + " "); // display it
		}
		System.out.println("");
	}
	
	public int size()
	{
		return nElems;
	}
	
	public boolean contains(long value)
	{
		return find(value)!=-1?true:false;
	}
	
} // end class HighArray

class HighArrayApp 
{
	public static void main(String[] args) {
		HighArray a = new HighArray(10);
		a.insert(1);
		a.insert(2);
		a.insert(2);
		a.insert(3);
		a.insert(3);
		a.insert(3);
		a.insert(3);
		a.insert(5);
		a.insert(6);
		a.insert(6);
		
		a.delete(1);
		a.delete(2);
		a.delete(4);
		a.delete(5);
		a.deleteAll(6);
		a.display();
	}
}